package hot100;

public class Lc230 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    private int ret;
    private int k;

    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return this.ret;
    }

    void dfs(TreeNode root) {
        if (k < 0) {
            return;
        }
        if (root.left != null) {
            dfs(root.left);
        }
        k -= 1;
        if (k == 0) {
            this.ret = root.val;
        }
        if (root.right != null) {
            dfs(root.right);
        }
    }
}
